A highly potent CXCR4 antagonist, compound 2, was previously found by using two orthogonal cyclic pentapeptide libraries involving conformation-based and sequence-based libraries based on the pharmacophore of a 14-mer peptidic antagonist, 1. Herein, cyclic tetrapeptides derived from replacements of the dipeptide unit (Nal-Gly) with a gamma-amino acid and pseudopeptides cyclized by disulfide and olefin bridges were synthesized to find novel scaffold structures different from that of cyclic pentapeptides. These compounds contain a reduced number of peptide bonds compared to compound 2. Furthermore, several analogues with chemical modification of the side chain of Arg(4) in 2 were also prepared. From these, several new leads possessing high to moderate CXCR4-antagonistic activity were characterized.